<!DOCTYPE html><html lang="zh-CN"><head><meta charset="UTF-8"><meta http-equiv="X-UA-Compatible" content="IE=edge"><meta name="viewport" content="width=device-width, initial-scale=1.0"><meta name="theme-color" content="#0078E7"><meta name="author" content="爱肖彤真是太好了"><meta name="copyright" content="爱肖彤真是太好了"><meta name="generator" content="Hexo 5.1.1"><meta name="theme" content="hexo-theme-yun"><title>redis底层数据结构解析 | 工藤旧二の博客</title><link rel="stylesheet" href="https://fonts.googleapis.com/css2?family=Noto+Serif+SC:wght@900&amp;display=swap" media="none" onload="this.media='all'"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/star-markdown-css@0.1.19/dist/yun/yun-markdown.min.css"><script src="//at.alicdn.com/t/font_1140697_stqaphw3j4.js" async></script><script src="https://cdn.jsdelivr.net/npm/scrollreveal/dist/scrollreveal.min.js" defer></script><script>document.addEventListener("DOMContentLoaded", () => {
  [".post-card",".post-content img"].forEach((target)=> {
    ScrollReveal().reveal(target);
  })
});
</script><link rel="shortcut icon" type="image/svg+xml" href="/task/yun.ico"><link rel="mask-icon" href="/task/yun.ico" color="#0078E7"><link rel="alternate icon" href="/yun.ico"><link rel="preload" href="/task/css/hexo-theme-yun.css" as="style"><link rel="preload" href="/task/js/utils.js" as="script"><link rel="preload" href="/task/js/hexo-theme-yun.js" as="script"><link rel="prefetch" href="/task/js/sidebar.js" as="script"><link rel="preconnect" href="https://cdn.jsdelivr.net" crossorigin><link rel="stylesheet" href="/task/css/hexo-theme-yun.css"><link rel="alternate" href="/task/atom.xml" title="工藤旧二の博客" type="application/atom+xml"><script id="yun-config">
    const Yun = window.Yun || {};
    window.CONFIG = {"root":"/task/","title":"工藤旧二の博客","version":"0.9.7","anonymous_image":"https://cdn.jsdelivr.net/gh/YunYouJun/cdn/img/avatar/none.jpg","say":{"api":"https://v1.hitokoto.cn","hitokoto":true},"local_search":{"path":"/task/search.xml"},"fireworks":{"colors":["102, 167, 221","62, 131, 225","33, 78, 194"]}};
  </script><script>(function(){
  var bp = document.createElement('script');
  var curProtocol = window.location.protocol.split(':')[0];
  if (curProtocol === 'https') {
    bp.src = 'https://zz.bdstatic.com/linksubmit/push.js';
  }
  else {
    bp.src = 'http://push.zhanzhang.baidu.com/push.js';
  }
  var s = document.getElementsByTagName("script")[0];
  s.parentNode.insertBefore(bp, s);
})();</script><meta name="description" content="redis底层数据结构解析 sds（简单动态字符串）redis并没有使用c语言中的字符串而是使用的自定义的sds，以解决一些c语言字符串会出现的问题以及进行性能优化 结构如下： len：当前字符串长度 free：分配的空间所剩余的长度 buf：字符串的实体（不包含结束符） 问题1：c的字符串本身不记录字符串长度，如果要获取字符串长度，时间复杂度为O(n)sds：数据结构中带有字符串的长度，和预留空">
<meta property="og:type" content="article">
<meta property="og:title" content="redis底层数据结构解析">
<meta property="og:url" content="http://huang_zhao.gitee.io/task/2021/07/07/%E6%95%B0%E6%8D%AE%E5%BA%93/redis/2021-07-07-redis%E5%BA%95%E5%B1%82%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E8%A7%A3%E6%9E%90/index.html">
<meta property="og:site_name" content="工藤旧二の博客">
<meta property="og:description" content="redis底层数据结构解析 sds（简单动态字符串）redis并没有使用c语言中的字符串而是使用的自定义的sds，以解决一些c语言字符串会出现的问题以及进行性能优化 结构如下： len：当前字符串长度 free：分配的空间所剩余的长度 buf：字符串的实体（不包含结束符） 问题1：c的字符串本身不记录字符串长度，如果要获取字符串长度，时间复杂度为O(n)sds：数据结构中带有字符串的长度，和预留空">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://tva1.sinaimg.cn/large/008i3skNly1gs8e92nvhkj318w0gqn0z.jpg">
<meta property="article:published_time" content="2021-07-07T07:12:11.000Z">
<meta property="article:modified_time" content="2021-07-08T11:07:09.000Z">
<meta property="article:author" content="爱肖彤真是太好了">
<meta property="article:tag" content="数据库">
<meta property="article:tag" content="redis">
<meta property="article:tag" content="数据结构">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://tva1.sinaimg.cn/large/008i3skNly1gs8e92nvhkj318w0gqn0z.jpg"><script src="/task/js/ui/mode.js"></script><link rel="stylesheet" href="/task/css/prism.css" type="text/css"></head><body><script defer src="https://cdn.jsdelivr.net/npm/animejs@latest/anime.min.js"></script><script defer src="/task/js/ui/fireworks.js"></script><canvas class="fireworks"></canvas><div class="container"><a class="sidebar-toggle hty-icon-button" id="menu-btn"><div class="hamburger hamburger--spin" type="button"><span class="hamburger-box"><span class="hamburger-inner"></span></span></div></a><div class="sidebar-toggle sidebar-overlay"></div><aside class="sidebar"><script src="/task/js/sidebar.js"></script><ul class="sidebar-nav"><li class="sidebar-nav-item sidebar-nav-toc hty-icon-button sidebar-nav-active" data-target="post-toc-wrap" title="文章目录"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-list-ordered"></use></svg></li><li class="sidebar-nav-item sidebar-nav-overview hty-icon-button" data-target="site-overview-wrap" title="站点概览"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-passport-line"></use></svg></li></ul><div class="sidebar-panel" id="site-overview-wrap"><div class="site-info fix-top"><a class="site-author-avatar" href="/task/about/" title="爱肖彤真是太好了"><img width="96" loading="lazy" src="/task/Yun.png" alt="爱肖彤真是太好了"></a><div class="site-author-name"><a href="/task/about/">爱肖彤真是太好了</a></div><a class="site-name" href="/task/about/site.html">工藤旧二の博客</a><sub class="site-subtitle"></sub><div class="site-desciption"></div></div><nav class="site-state"><a class="site-state-item hty-icon-button icon-home" href="/task/" title="首页"><span class="site-state-item-icon"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-home-4-line"></use></svg></span></a><div class="site-state-item"><a href="/task/archives/" title="归档"><span class="site-state-item-icon"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-archive-line"></use></svg></span><span class="site-state-item-count">57</span></a></div><div class="site-state-item"><a href="/task/categories/" title="分类"><span class="site-state-item-icon"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-folder-2-line"></use></svg></span><span class="site-state-item-count">2</span></a></div><div class="site-state-item"><a href="/task/tags/" title="标签"><span class="site-state-item-icon"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-price-tag-3-line"></use></svg></span><span class="site-state-item-count">50</span></a></div><a class="site-state-item hty-icon-button" target="_blank" rel="noopener" href="https://yun.yunyoujun.cn" title="文档"><span class="site-state-item-icon"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-settings-line"></use></svg></span></a></nav><hr style="margin-bottom:0.5rem"><div class="links-of-author"><a class="links-of-author-item hty-icon-button" rel="noopener" title="RSS" target="_blank" style="color:orange"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-rss-line"></use></svg></a><a class="links-of-author-item hty-icon-button" rel="noopener" title="QQ" target="_blank" style="color:#12B7F5"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-qq-line"></use></svg></a><a class="links-of-author-item hty-icon-button" rel="noopener" title="GitHub" target="_blank" style="color:#6e5494"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-github-line"></use></svg></a><a class="links-of-author-item hty-icon-button" rel="noopener" title="微博" target="_blank" style="color:#E6162D"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-weibo-line"></use></svg></a><a class="links-of-author-item hty-icon-button" rel="noopener" title="豆瓣" target="_blank" style="color:#007722"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-douban-line"></use></svg></a><a class="links-of-author-item hty-icon-button" rel="noopener" href="https://music.163.com/#/user/home?id=552858287" title="网易云音乐" target="_blank" style="color:#C20C0C"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-netease-cloud-music-line"></use></svg></a><a class="links-of-author-item hty-icon-button" rel="noopener" title="知乎" target="_blank" style="color:#0084FF"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-zhihu-line"></use></svg></a><a class="links-of-author-item hty-icon-button" rel="noopener" href="https://space.bilibili.com/15081363" title="哔哩哔哩" target="_blank" style="color:#FF8EB3"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-bilibili-line"></use></svg></a><a class="links-of-author-item hty-icon-button" rel="noopener" title="Twitter" target="_blank" style="color:#1da1f2"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-twitter-line"></use></svg></a><a class="links-of-author-item hty-icon-button" rel="noopener" title="Telegram Channel" target="_blank" style="color:#0088CC"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-telegram-line"></use></svg></a><a class="links-of-author-item hty-icon-button" rel="noopener" title="E-Mail" target="_blank" style="color:#8E71C1"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-mail-line"></use></svg></a><a class="links-of-author-item hty-icon-button" rel="noopener" title="Travelling" target="_blank" style="color:var(--hty-text-color)"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-send-plane-2-line"></use></svg></a></div><hr style="margin:0.5rem 1rem"><div class="links"><a class="links-item hty-icon-button" href="/task/links/" title="我的小伙伴们" style="color:dodgerblue"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-genderless-line"></use></svg></a></div><br><a class="links-item hty-icon-button" id="toggle-mode-btn" href="javascript:;" title="Mode" style="color: #f1cb64"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-contrast-2-line"></use></svg></a></div><div class="sidebar-panel sidebar-panel-active" id="post-toc-wrap"><div class="post-toc"><div class="post-toc-content"><ol class="toc"><li class="toc-item toc-level-2"><a class="toc-link" href="#redis%E5%BA%95%E5%B1%82%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E8%A7%A3%E6%9E%90"><span class="toc-text">redis底层数据结构解析</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#sds%EF%BC%88%E7%AE%80%E5%8D%95%E5%8A%A8%E6%80%81%E5%AD%97%E7%AC%A6%E4%B8%B2%EF%BC%89"><span class="toc-text">sds（简单动态字符串）</span></a><ol class="toc-child"><li class="toc-item toc-level-5"><a class="toc-link" href="#%E9%97%AE%E9%A2%981%EF%BC%9Ac%E7%9A%84%E5%AD%97%E7%AC%A6%E4%B8%B2%E6%9C%AC%E8%BA%AB%E4%B8%8D%E8%AE%B0%E5%BD%95%E5%AD%97%E7%AC%A6%E4%B8%B2%E9%95%BF%E5%BA%A6%EF%BC%8C%E5%A6%82%E6%9E%9C%E8%A6%81%E8%8E%B7%E5%8F%96%E5%AD%97%E7%AC%A6%E4%B8%B2%E9%95%BF%E5%BA%A6%EF%BC%8C%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6%E4%B8%BAO-n"><span class="toc-text">问题1：c的字符串本身不记录字符串长度，如果要获取字符串长度，时间复杂度为O(n)</span></a></li><li class="toc-item toc-level-5"><a class="toc-link" href="#%E9%97%AE%E9%A2%982%EF%BC%9Ac%E4%B8%AD%E7%9A%84%E5%AD%97%E7%AC%A6%E4%B8%B2%E4%B8%8D%E8%AE%B0%E5%BD%95%E8%87%AA%E8%BA%AB%E9%95%BF%E5%BA%A6%E5%AE%B9%E6%98%93%E9%80%A0%E6%88%90%E7%BC%93%E5%86%B2%E5%8C%BA%E6%BA%A2%E5%87%BA"><span class="toc-text">问题2：c中的字符串不记录自身长度容易造成缓冲区溢出</span></a></li><li class="toc-item toc-level-5"><a class="toc-link" href="#%E9%97%AE%E9%A2%983%EF%BC%9A%E7%BB%8F%E5%B8%B8%E4%BF%AE%E6%94%B9%E5%AD%97%E7%AC%A6%E4%B8%B2%E4%BC%9A%E9%A2%91%E7%B9%81%E4%BF%AE%E6%94%B9%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%9A%84%E7%A9%BA%E9%97%B4%E5%88%86%E9%85%8D%EF%BC%8C%E5%BD%B1%E5%93%8D%E6%80%A7%E8%83%BD"><span class="toc-text">问题3：经常修改字符串会频繁修改字符串的空间分配，影响性能</span></a></li></ol></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8%EF%BC%88listnode%EF%BC%89"><span class="toc-text">双向链表（listnode）</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%8E%8B%E7%BC%A9%E5%88%97%E8%A1%A8%EF%BC%88ziplist%EF%BC%89"><span class="toc-text">压缩列表（ziplist）</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%93%88%E5%B8%8C%E8%A1%A8"><span class="toc-text">哈希表</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%95%B4%E6%95%B0%E9%9B%86%E5%90%88"><span class="toc-text">整数集合</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E8%B7%B3%E8%A1%A8"><span class="toc-text">跳表</span></a></li></ol></li></ol></div></div></div></aside><main class="sidebar-translate" id="content"><div id="post"><article class="post-block" itemscope itemtype="https://schema.org/Article"><link itemprop="mainEntityOfPage" href="http://huang_zhao.gitee.io/task/task/2021/07/07/%E6%95%B0%E6%8D%AE%E5%BA%93/redis/2021-07-07-redis%E5%BA%95%E5%B1%82%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E8%A7%A3%E6%9E%90/"><span hidden itemprop="author" itemscope itemtype="https://schema.org/Person"><meta itemprop="name" content="爱肖彤真是太好了"><meta itemprop="description"></span><span hidden itemprop="publisher" itemscope itemtype="https://schema.org/Organization"><meta itemprop="name" content="工藤旧二の博客"></span><header class="post-header"><h1 class="post-title" itemprop="name headline">redis底层数据结构解析</h1><div class="post-meta"><div class="post-time" style="display:block"><span class="post-meta-item-icon"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-calendar-line"></use></svg></span> <time title="创建时间：2021-07-07 15:12:11" itemprop="dateCreated datePublished" datetime="2021-07-07T15:12:11+08:00">2021-07-07</time><span class="post-meta-divider">-</span><span class="post-meta-item-icon"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-calendar-2-line"></use></svg></span> <time title="修改时间：2021-07-08 19:07:09" itemprop="dateModified" datetime="2021-07-08T19:07:09+08:00">2021-07-08</time></div><span class="post-count"><span class="post-symbolcount"><span class="post-meta-item-icon" title="本文字数"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-file-word-line"></use></svg></span> <span title="本文字数">986</span><span class="post-meta-divider">-</span><span class="post-meta-item-icon" title="阅读时长"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-timer-line"></use></svg></span> <span title="阅读时长">3m</span></span></span><span class="post-busuanzi"><span class="post-meta-divider">-</span><span class="post-meta-item-icon" title="阅读次数"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-eye-line"></use></svg> <span id="busuanzi_value_page_pv"></span></span></span><div class="post-classify"><span class="post-category"><span class="post-meta-item-icon"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-folder-line"></use></svg></span> <span itemprop="about" itemscope itemtype="https://schema.org/Thing"><a class="category" href="/task/categories/%E6%8A%80%E6%9C%AF%E5%88%86%E4%BA%AB/" style="--text-color:var(--hty-text-color)" itemprop="url" rel="index"><span itemprop="text">技术分享</span></a></span></span><span class="post-tag"><span class="post-meta-divider">-</span><a class="tag" href="/task/tags/%E6%95%B0%E6%8D%AE%E5%BA%93/" style="--text-color:var(--hty-text-color)"><span class="post-meta-item-icon"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-price-tag-3-line"></use></svg></span><span class="tag-name">数据库</span></a><a class="tag" href="/task/tags/redis/" style="--text-color:var(--hty-text-color)"><span class="post-meta-item-icon"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-price-tag-3-line"></use></svg></span><span class="tag-name">redis</span></a><a class="tag" href="/task/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/" style="--text-color:var(--hty-text-color)"><span class="post-meta-item-icon"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-price-tag-3-line"></use></svg></span><span class="tag-name">数据结构</span></a></span></div></div></header><section class="post-body" itemprop="articleBody"><div class="post-content markdown-body" style="--smc-primary:#0078E7;"><h2 id="redis底层数据结构解析"><a href="#redis底层数据结构解析" class="headerlink" title="redis底层数据结构解析"></a>redis底层数据结构解析</h2><p><img src="https://tva1.sinaimg.cn/large/008i3skNly1gs8e92nvhkj318w0gqn0z.jpg" alt="image-20210707145917303" loading="lazy"></p>
<h3 id="sds（简单动态字符串）"><a href="#sds（简单动态字符串）" class="headerlink" title="sds（简单动态字符串）"></a>sds（简单动态字符串）</h3><p>redis并没有使用c语言中的字符串而是使用的自定义的sds，以解决一些c语言字符串会出现的问题以及进行性能优化</p>
<p>结构如下：</p>
<p>len：当前字符串长度</p>
<p>free：分配的空间所剩余的长度</p>
<p>buf：字符串的实体（不包含结束符）</p>
<h5 id="问题1：c的字符串本身不记录字符串长度，如果要获取字符串长度，时间复杂度为O-n"><a href="#问题1：c的字符串本身不记录字符串长度，如果要获取字符串长度，时间复杂度为O-n" class="headerlink" title="问题1：c的字符串本身不记录字符串长度，如果要获取字符串长度，时间复杂度为O(n)"></a>问题1：c的字符串本身不记录字符串长度，如果要获取字符串长度，时间复杂度为O(n)</h5><p>sds：数据结构中带有字符串的长度，和预留空间的长度</p>
<h5 id="问题2：c中的字符串不记录自身长度容易造成缓冲区溢出"><a href="#问题2：c中的字符串不记录自身长度容易造成缓冲区溢出" class="headerlink" title="问题2：c中的字符串不记录自身长度容易造成缓冲区溢出"></a>问题2：c中的字符串不记录自身长度容易造成缓冲区溢出</h5><p>sds：当数据修改时，先判断内部的free是否满足容纳新字符串，如果不够就先进行扩容，扩容规则为：若数据长度小于1m就翻倍，大于1m就每次+1m</p>
<h5 id="问题3：经常修改字符串会频繁修改字符串的空间分配，影响性能"><a href="#问题3：经常修改字符串会频繁修改字符串的空间分配，影响性能" class="headerlink" title="问题3：经常修改字符串会频繁修改字符串的空间分配，影响性能"></a>问题3：经常修改字符串会频繁修改字符串的空间分配，影响性能</h5><p>sds：</p>
<ul>
<li>空间预分配<ul>
<li>就是指sds进行空间扩容时的规则，并不会只扩容所需的内存，通常情况会剩余一些额外的内存以便下次扩容使用</li>
</ul>
</li>
<li>惰性空间释放<ul>
<li>若修改sds减少时，并不会像想象中的减少对其所分配的内存，而是先将不用的内存放入free中，以便下次扩容，当然也有对应的主动释放空间的api</li>
</ul>
</li>
</ul>
<p>问题4：特殊字符保存</p>
<p>sds：sds是对二进制安全的，不会对数据做任何限制，也可以保存特殊字符，因为读取数据的判断是根据len，而不是结束符</p>
<h3 id="双向链表（listnode）"><a href="#双向链表（listnode）" class="headerlink" title="双向链表（listnode）"></a>双向链表（listnode）</h3><ul>
<li>双端：链表节点带有pre 和 next 指针，获取某个节点的前置节点和后置节点的复杂度为O(n)</li>
<li>无环：表头的节点 head 的prev指针和 表尾节点 next 都指向了Null，说明链表的访问结束了</li>
<li>获取链表长度：list 的len 属性，可以直接获取链表的长度，复杂度O(1)</li>
<li>多态：链表节点使用void* 指针来保存节点值，可以保存各种不同类型的值。</li>
<li>获取表头和表尾数据负责度O(1)</li>
</ul>
<h3 id="压缩列表（ziplist）"><a href="#压缩列表（ziplist）" class="headerlink" title="压缩列表（ziplist）"></a>压缩列表（ziplist）</h3><p>是一种特殊的双向链表</p>
<p>压缩链表与经典双端链表最大的区别在于，双端链表的节点是分散在内存中并不是连续的，压缩链表中所有的数据都是存储在一段连续的内存之中的,时间换空间。</p>
<p>具体内部参数：<a target="_blank" rel="noopener" href="https://juejin.cn/post/6974706255138914341#heading-6">https://juejin.cn/post/6974706255138914341#heading-6</a></p>
<h3 id="哈希表"><a href="#哈希表" class="headerlink" title="哈希表"></a>哈希表</h3><p>本质是一个列表，列表内部的元素是一个链表，链表的每一个结点存着键值对</p>
<p>这种方式叫做<strong>链地址法</strong>，用于解决hash冲突，在数组桶位相同的情况下将插入的结点插入到链表表头，所以hash在插入寻址的时间复杂度是o1</p>
<pre class=" language-c"><code class="language-c"><span class="token keyword">typedef</span> <span class="token keyword">struct</span> dictht<span class="token punctuation">{</span>
    <span class="token comment" spellcheck="true">// 哈希表数组</span>
    dictEntry <span class="token operator">*</span><span class="token operator">*</span>table<span class="token punctuation">;</span>

    <span class="token comment" spellcheck="true">// 哈希表大小</span>
    <span class="token keyword">unsigned</span> <span class="token keyword">long</span> size<span class="token punctuation">;</span>

    <span class="token comment" spellcheck="true">// 哈希表大小掩码，用于计算索引值</span>
    <span class="token comment" spellcheck="true">// 总是等于 size-1</span>
    <span class="token keyword">unsigned</span> <span class="token keyword">long</span> sizemask<span class="token punctuation">;</span>

    <span class="token comment" spellcheck="true">// 该哈希表已有节点数量</span>
    <span class="token keyword">unsigned</span> <span class="token keyword">long</span> used<span class="token punctuation">;</span>
<span class="token punctuation">}</span> dictht

</code></pre>
<p>结点</p>
<pre class=" language-c"><code class="language-c"><span class="token keyword">typedef</span> <span class="token keyword">struct</span> dictEntry <span class="token punctuation">{</span>
    <span class="token comment" spellcheck="true">// 键</span>
    <span class="token keyword">void</span> <span class="token operator">*</span>key<span class="token punctuation">;</span>

    <span class="token comment" spellcheck="true">// 值</span>
    <span class="token keyword">union</span> <span class="token punctuation">{</span>
        <span class="token keyword">void</span> <span class="token operator">*</span>val<span class="token punctuation">;</span>
        unit64_t u64<span class="token punctuation">;</span>
        nit64_t s64<span class="token punctuation">;</span>
    <span class="token punctuation">}</span> v<span class="token punctuation">;</span>

    <span class="token comment" spellcheck="true">// 指向下一个哈希表节点，形成链表</span>
    <span class="token keyword">struct</span> dictEntry <span class="token operator">*</span>next<span class="token punctuation">;</span>
<span class="token punctuation">}</span> dictEntry<span class="token punctuation">;</span>

</code></pre>
<h3 id="整数集合"><a href="#整数集合" class="headerlink" title="整数集合"></a>整数集合</h3><p>是redis中set的底层实现之一，使用场景比较少</p>
<p>它的特点有：</p>
<p><strong>元素类型只能为数字。<br>元素有三种类型：int16_t、int32_t、int64_t。<br>元素有序，不可重复。<br>内存连续，来节省内存空间。</strong></p>
<h3 id="跳表"><a href="#跳表" class="headerlink" title="跳表"></a>跳表</h3><p>个人总结</p>
<p>跳表是一种特殊的数据结构，存在多层次链表，每上一层链表都是下一层链表的子集，每一层可以看做是索引层</p>
<p><a target="_blank" rel="noopener" href="https://juejin.cn/post/6974706255138914341#heading-4">https://juejin.cn/post/6974706255138914341#heading-4</a></p>
</div><div id="reward-container"><span class="hty-icon-button button-glow" id="reward-button" title="打赏" onclick="var qr = document.getElementById(&quot;qr&quot;); qr.style.display = (qr.style.display === &quot;none&quot;) ? &quot;block&quot; : &quot;none&quot;;"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-hand-coin-line"></use></svg></span><div id="reward-comment">点我就给你看点有意思的</div><div id="qr" style="display:none;"><div style="display:inline-block"><a target="_blank" rel="noopener" href="https://gitee.com/huang_zhao/hz/raw/master/hz/alipay.png"><img loading="lazy" src="https://gitee.com/huang_zhao/hz/raw/master/hz/alipay.png" alt="支付宝" title="支付宝"></a><div><span style="color:#00A3EE"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-alipay-line"></use></svg></span></div></div><div style="display:inline-block"><a target="_blank" rel="noopener" href="https://gitee.com/huang_zhao/hz/raw/master/hz/qqpay.jpg"><img loading="lazy" src="https://gitee.com/huang_zhao/hz/raw/master/hz/qqpay.jpg" alt="QQ 支付" title="QQ 支付"></a><div><span style="color:#12B7F5"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-qq-line"></use></svg></span></div></div><div style="display:inline-block"><a target="_blank" rel="noopener" href="https://gitee.com/huang_zhao/hz/raw/master/hz/wxpay.jpg"><img loading="lazy" src="https://gitee.com/huang_zhao/hz/raw/master/hz/wxpay.jpg" alt="微信支付" title="微信支付"></a><div><span style="color:#2DC100"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-wechat-pay-line"></use></svg></span></div></div></div></div><ul class="post-copyright"><li class="post-copyright-author"><strong>本文作者：</strong>爱肖彤真是太好了</li><li class="post-copyright-link"><strong>本文链接：</strong><a href="http://huang_zhao.gitee.io/task/2021/07/07/%E6%95%B0%E6%8D%AE%E5%BA%93/redis/2021-07-07-redis%E5%BA%95%E5%B1%82%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E8%A7%A3%E6%9E%90/" title="redis底层数据结构解析">http://huang_zhao.gitee.io/task/2021/07/07/%E6%95%B0%E6%8D%AE%E5%BA%93/redis/2021-07-07-redis%E5%BA%95%E5%B1%82%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E8%A7%A3%E6%9E%90/</a></li><li class="post-copyright-license"><strong>版权声明：</strong>本博客所有文章除特别声明外，均默认采用 <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh" target="_blank" rel="noopener" title="CC BY-NC-SA 4.0 "><svg class="icon"><use xlink:href="#icon-creative-commons-line"></use></svg><svg class="icon"><use xlink:href="#icon-creative-commons-by-line"></use></svg><svg class="icon"><use xlink:href="#icon-creative-commons-nc-line"></use></svg><svg class="icon"><use xlink:href="#icon-creative-commons-sa-line"></use></svg></a> 许可协议。</li></ul></section></article><div class="post-nav"><div class="post-nav-item"><a class="post-nav-prev" href="/task/2021/07/14/%E6%95%B0%E6%8D%AE%E5%BA%93/redis/redis%E4%B8%BA%E4%BB%80%E4%B9%88%E8%BF%99%E4%B9%88%E5%BF%AB-%E8%A7%A3%E5%86%B3hash%E5%86%B2%E7%AA%81%E7%9A%84%E9%97%A8%E9%81%93/" rel="prev" title="redis为什么这么快-解决hash冲突的门道"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-arrow-left-s-line"></use></svg><span class="post-nav-text">redis为什么这么快-解决hash冲突的门道</span></a></div><div class="post-nav-item"><a class="post-nav-next" href="/task/2021/07/02/python/%E5%AD%A6%E4%B9%A0/%E5%88%86%E5%B8%83%E5%BC%8F%E9%94%81/" rel="next" title="python实现分布式锁"><span class="post-nav-text">python实现分布式锁</span><svg class="icon" aria-hidden="true"><use xlink:href="#icon-arrow-right-s-line"></use></svg></a></div></div></div></main><footer class="sidebar-translate" id="footer"><div class="copyright"><span>&copy; 2019 – 2022 </span><span class="with-love" id="animate"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-cloud-line"></use></svg></span><span class="author"> 爱肖彤真是太好了</span></div><div class="powered"><span>由 <a href="https://hexo.io" target="_blank" rel="noopener">Hexo</a> 驱动 v5.1.1</span><span class="footer-separator">|</span><span>主题 - <a rel="noopener" href="https://github.com/YunYouJun/hexo-theme-yun" target="_blank"><span>Yun</span></a> v0.9.7</span></div><div class="live_time"><span>本博客已萌萌哒地运行</span><span id="display_live_time"></span><span class="moe-text">(●'◡'●)</span><script>function blog_live_time() {
  window.setTimeout(blog_live_time, 1000);
  const start = new Date('2019-04-12T00:00:00');
  const now = new Date();
  const timeDiff = (now.getTime() - start.getTime());
  const msPerMinute = 60 * 1000;
  const msPerHour = 60 * msPerMinute;
  const msPerDay = 24 * msPerHour;
  const passDay = Math.floor(timeDiff / msPerDay);
  const passHour = Math.floor((timeDiff % msPerDay) / 60 / 60 / 1000);
  const passMinute = Math.floor((timeDiff % msPerHour) / 60 / 1000);
  const passSecond = Math.floor((timeDiff % msPerMinute) / 1000);
  display_live_time.innerHTML = " " + passDay + " 天 " + passHour + " 小时 " + passMinute + " 分 " + passSecond + " 秒";
}
blog_live_time();
</script></div><div id="busuanzi"><script async src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script><span id="busuanzi_container_site_uv" title="总访客量"><span><svg class="icon" aria-hidden="true"><use xlink:href="#icon-user-line"></use></svg></span><span id="busuanzi_value_site_uv"></span></span><span class="footer-separator">|</span><span id="busuanzi_container_site_pv" title="总访问量"><span><svg class="icon" aria-hidden="true"><use xlink:href="#icon-eye-line"></use></svg></span><span id="busuanzi_value_site_pv"></span></span></div></footer><a class="hty-icon-button" id="goUp" aria-label="back-to-top" href="#"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-arrow-up-s-line"></use></svg><svg class="progress-circle-container" viewBox="0 0 100 100"><circle class="progress-circle" id="progressCircle" cx="50" cy="50" r="48" fill="none" stroke="#0078E7" stroke-width="2" stroke-linecap="round"></circle></svg></a><a class="popup-trigger hty-icon-button icon-search" id="search" href="javascript:;" title="搜索"><span class="site-state-item-icon"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-search-line"></use></svg></span></a><script>window.addEventListener("DOMContentLoaded", () => {
  // Handle and trigger popup window
  document.querySelector(".popup-trigger").addEventListener("click", () => {
    document.querySelector(".popup").classList.add("show");
    setTimeout(() => {
      document.querySelector(".search-input").focus();
    }, 100);
  });

  // Monitor main search box
  const onPopupClose = () => {
    document.querySelector(".popup").classList.remove("show");
  };

  document.querySelector(".popup-btn-close").addEventListener("click", () => {
    onPopupClose();
  });

  window.addEventListener("keyup", event => {
    if (event.key === "Escape") {
      onPopupClose();
    }
  });
});
</script><script src="/task/js/search/local-search.js" defer></script><div class="popup search-popup"><div class="search-header"><span class="popup-btn-close close-icon hty-icon-button"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-close-line"></use></svg></span></div><div class="search-input-container"><input class="search-input" id="local-search-input" type="text" placeholder="搜索..." value=""></div><div id="local-search-result"></div></div></div><script defer src="/task/js/utils.js"></script><script defer src="/task/js/hexo-theme-yun.js"></script></body></html>